15-112
Summer 19

Home

Syllabus

Schedule

Gallery

Staff

Piazza

Autolab

OH Queue

CMU 15-112: Fundamentals of Programming and Computer Science
Day12 Practice (Due never)


  1. Review course notes
    Here are some important things to understand from the course notes:
    1. The fact that logn is much, much smaller than n.
    2. Why we ignore lower-order terms and constants in Big-O.
    3. Why we ignore the base in logs in Big-O.
    4. How selectionSort, bubbleSort, and mergesort work.
    5. The proof that selectionSort is O(n2).
    6. The proof that, for selectionSort (or any quadratic algorithm), when you multiply the input size by c, you multiply the runtime by c2.
    7. The proof that mergesort is O(nlogn).
    8. The fact that, for mergesort (or any nlogn algorithm), when you multiply the input size by c, you multiply the runtime by a value slightly larger than c but quite a bit smaller than c2.
    9. The fact that O(nlogn) is theoretically optimal for any comparison-based sort, and consequently that mergesort is within a constant time as fast as any possible comparison-based sort.

  2. Review xSortLab
    1. Do a visual sort of bubbleSort, and predict each step before confirming it visually.
    2. Do a visual sort of selectionSort, and predict each step before confirming it visually.
    3. Do a visual sort of mergesort, and predict each step before confirming it visually.
    4. Do a timed sort of selectionSort, and confirm that doubling the input size increases the runtime by about 4x, and that this prediction grows more accurate as the input size increases.
    5. Do a timed sort of mergesort, and confirm that doubling the input size increases the runtime by more than 2x, but just barely, and well under 4x, and that this prediction grows more accurate as the input size increases.

  3. Big-O Analysis
    What is the Big-O of each of the following functions?
    def bigO1(s): charCount="" for c in s: count = s.count(c) if c in charCount: continue else: charCount += "%s%d " % (c, count) def bigO2(s): myS = s * len(s) result = "" for c in myS: if c in result: break else: result += c return result def bigO3(a): for i in range(len(a)): j=1 while j < len(a): j *= 2 print(a) def bigO4(L): # assume L is a 1d list N = len(L) n = len(L) while (n > 0): print(max(L[0:N])) n //= 4 def bigO5(L): # assume L is a 1d list N = len(L) for i in range(N): for j in range(i, N): if (L[i] > L[j]): (L[i], L[j]) = (L[j], L[i])

  4. mostCommonName(L) in O(n) time
    Write the function mostCommonName, that takes a list of names (such as ["Jane", "Aaron", "Cindy", "Aaron"], and returns the most common name in this list (in this case, "Aaron"). If there is more than one such name, return a set of the most common names. So mostCommonName(["Jane", "Aaron", "Jane", "Cindy", "Aaron"]) returns the set {"Aaron", "Jane"}. If the set is empty, return None. Also, treat names case sensitively, so "Jane" and "JANE" are different names. You should write three different versions, one that runs in O(n**2), O(nlogn) and O(n).
    def mostCommonName(L): return 42 # place your answer here! def testMostCommonName(): print("Testing mostCommonName()...", end="") assert(mostCommonName(["Jane", "Aaron", "Cindy", "Aaron"]) == "Aaron") assert(mostCommonName(["Jane", "Aaron", "Jane", "Cindy", "Aaron"]) == {"Aaron", "Jane"}) assert(mostCommonName(["Cindy"]) == "Cindy") assert(mostCommonName(["Jane", "Aaron", "Cindy"]) == {"Aaron", "Cindy", "Jane"}) assert(mostCommonName([]) == None) print("Passed!") testMostCommonName()

  5. getPairSum(a, target) in O(n) time
    Write the function getPairSum(a, target) that takes a list of numbers and a target value (also a number), and if there is a pair of numbers in the given list that add up to the given target number, returns that pair, and otherwise returns an empty list. If there is more than one valid pair, you can return any of them. You should write two different versions, one that runs in O(n**2) and the other in O(n). For example: 
    getPairSum([1],1) == []
getPairSum([5,2],7) in [ [5,2], [2,5] ]
getPairSum([10,-1,1,-8,3,1], 2) in [ [10,-8], [-8,10] ] (can also return [-1,3] or [1,1])
getPairSum([10,-1,1,-8,3,1],10) == []
    def getPairSum(a, target): return 42 # place your answer here! def testGetPairSum(): print("Testing getPairSum...", end="") assert(getPairSum([1],1) == []) assert(getPairSum([5, 2], 7) in [ [5, 2], [2, 5] ]) # (can return [10, -8] or [-1,3] or [1,1]) assert(getPairSum([10,-1,1,-8,3,1], 2) in [[10, -8], [-8, 10], [-1, 3], [3, -1], [1, 1]]) assert(getPairSum([10,-1,1,-8,3,1], 10) == []) assert(getPairSum([1, 4, 3], 2) == []) print("Passed!") testGetPairSum()

  6. mergeSortWithOneAuxList(a)
    Write the function mergeSortWithOneAuxList(a) that works just like mergeSort from the notes, only here you can only create a single aux list just one time, rather than once for each call to merge. To do this, you will need to create the aux list in the outer function (mergeSortWithOneAuxList) and then pass it as a parameter into the merge function. The rest is left to you. In a comment at the top of this function, include some timing measurements comparing this function to the original mergeSort, and a brief reflection on whether or not this change was worthwhile.

  7. More Big-O Analysis (with solns available)
    Problems
    Mild
    Problem 1 
    def foo(L): #L is a list
    i = 1
    listLength = len(L)
    result = []
    while i < listLength:
        result += L[i]
        i *= 3
    return i
    Problem 2 
    def foo(S): #S is a string
    stringLength = len(S)
    i = stringLength
    result = {}
    while i > 0:
        result.add(S[i])
        i //= 3
    return result
    Problem 3 
    def foo(L): # L is a list
    lenList = len(L)
    count = 0
    for i in range(lenList):
        for j in range(lenList):
            count += L[i]
    return count
    Medium
    Problem 4 
    def foo(s): #s is a string of length N
    result = 0
    for char in string.ascii_lowercase:
        if char in s:
            s = s[1:]
            result += 1
    return result
    Problem 5 
    def foo(s):
    return len(s)
    Problem 6 
    def foo(L): #L is a list
    n = len(L)
    for i in range(n**2, n**3, n):
        L.append(i)
    for j in range(n//5, n//2, n//10):
        L.pop()
    return L
    Hard
    Problem 7 
    def foo(L):
    result = []
    for i in range(1, len(sorted(L)) + 1):
        newList = len(L) * [i]
        result.extend(newList)
    return sorted(result)
    Problem 8 
    def foo(L): # L is a square, 2D list
    n = len(L)
    j = 1
    count = 0
    while j < n:
        for i in range(n):
            if max(L[j]) in L[i]:
                count += 1
        j *= 2
    return count
    Problem 9 
    def bigOh(L):
    new = list()
    for i in range(len(L)):
        new.extend(L[:i:2])
    new.sort()
    result = set(new)
    return result